package com.klun.project.common.constans.leetcode;
//给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
// 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
//
// 示例 1：
//输入：root = [1,null,2,null,3,null,4,null,null]
//输出：[2,1,3,null,null,null,4]
//解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
//
// 示例 2：
//输入: root = [2,1,3]
//输出: [2,1,3]
// 提示：
// 树节点的数目在 [1, 104] 范围内。
// 1 <= Node.val <= 105
// Related Topics 贪心 树 深度优先搜索 二叉搜索树 分治 二叉树
// 👍 151 👎 0

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayList;
import java.util.List;

public class Solution1382 {
	List<Integer> inorderSeq = new ArrayList<>();

	public TreeNode balanceBST(TreeNode root) {
		getInorder(root);
		return build(0, inorderSeq.size() - 1);
	}

	public void getInorder(TreeNode o) {
		if (o.left != null) {
			getInorder(o.left);
		}
		inorderSeq.add(o.val);
		if (o.right != null) {
			getInorder(o.right);
		}
	}

	public TreeNode build(int start, int end) {
		if (start > end) return null;
		int mid = (start + end) / 2;
		TreeNode root = new TreeNode(inorderSeq.get(mid));
		root.left = build(start, mid - 1);
		root.right = build(mid + 1, end);
		return root;
	}


	public static void main(String[] args) {
		Solution1382 solution = new Solution1382();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		TreeNode treeNode = ParseUtils.ArrayToBTree("[1,null,2,null,3,null,4,null,null]");
		TreeNode treeNode1 = solution.balanceBST(treeNode);
		System.out.println(treeNode1);
	}
}
